/**
 * 给你一个整数数组nums 以及两个整数lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含lower和upper）之内的 区间和的个数 。
 *
 * 区间和S(i, j)表示在nums中，位置从i到j的元素之和，包含i和j(i ≤ j)。
 *
 * 链接：https://leetcode.cn/problems/count-of-range-sum
 * 详解：https://labuladong.gitee.io/algo/2/21/41/
 */
class CountRangeSum {
    int lower;
    int upper;
    public int countRangeSum(int[] nums, int lower, int upper) {
        this.lower=lower;
        this.upper=upper;
        int len=nums.length;
        long[] preSum=new long[len+1];
        for(int i=1;i<=len;i++) {
            preSum[i]=preSum[i-1]+(long)nums[i-1];
        }
        return mergeSort(preSum,0,len);
    }
    public int mergeSort(long[] preSum,int left,int right) {
        if(left>=right) {
            return 0;
        }
        int mid=left+((right-left)>>>1);
        int leftCount=mergeSort(preSum,left,mid);
        int rightCount=mergeSort(preSum,mid+1,right);
        int crossCount=merge(preSum,left,mid,right);
        return leftCount+rightCount+crossCount;
    }
    public int merge(long[] preSum,int left,int mid,int right) {
        int start=mid+1;
        int end=mid+1;
        int count=0;
        for(int i=left;i<=mid;i++) {
            while(start<=right&&preSum[start]-preSum[i]<lower) {
                start++;
            }
            while(end<=right&&preSum[end]-preSum[i]<=upper) {
                end++;
            }
            // if(start>right) {
            //     break;
            // }
            count+=(end-start);
        }
        long[] tmp=new long[right-left+1];
        int k=0;
        int s1=left;
        int b1=mid;
        int s2=mid+1;
        int b2=right;
        while(s1<=b1&&s2<=b2) {
            if(preSum[s1]<preSum[s2]) {
                tmp[k++]=preSum[s1++];
            } else {
                tmp[k++]=preSum[s2++];
            }
        }
        while(s1<=b1) {
            tmp[k++]=preSum[s1++];
        }
        while(s2<=b2) {
            tmp[k++]=preSum[s2++];
        }
        for(int i=0;i<k;i++) {
            preSum[i+left]=tmp[i];
        }
        return count;
    }
}